// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math/rand"
)

func ArraySort(array []int) []int {
	quickSortDesc(array, 0, len(array)-1)
	return array
}

func quickSortDesc(array []int, low, high int) {
	if low >= high {
		return
	}
	k := rand.Intn(high-low+1) + low
	tmp := array[high]
	array[high] = array[k]
	array[k] = tmp

	pivot := array[high]
	j := low - 1
	for i := low; i < high; i++ {
		if array[i] >= pivot {
			j++
			tmp := array[j]
			array[j] = array[i]
			array[i] = tmp
		}
	}
	tmp = array[j+1]
	array[j+1] = array[high]
	array[high] = tmp

	quickSortDesc(array, low, j)
	quickSortDesc(array, j+1, high)
}

func main() {
	array := []int{33, 23, 56, 7, 8, 18, 99, 28}
	res := ArraySort(array)
	fmt.Println(res)
}

//$ go run interview6-9.go
//[99 56 33 28 23 18 8 7]
